﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace CSharpAlgorithm
{
    class NewEstTest02
    {
        public NewEstTest02()
        {
            int testCase = Int32.Parse(TestConsole.ReadLine());
            while (testCase-- > 0)
            {
                string[] input = TestConsole.ReadLine().Split(' ');
                int rightCount = Int32.Parse(input[0]);
                int orderCount = Int32.Parse(input[1]);
                int[,] order = new int[rightCount + 1, rightCount + 1];
                List<int[]> roundList = new List<int[]>();
                //입력
                for (int i = 0; i < orderCount; i++)
                {
                    input = TestConsole.ReadLine().Split(' ');
                    int from = Int32.Parse(input[0]);
                    int to = Int32.Parse(input[1]);
                    order[from, to] = 1;
                    order[0, to]++; //자신을 킬 수 있는 전구가 몇개인지...
                    roundList.Add(new int[2] { from, to });
                }
                List<int[]> loop = new List<int[]>();
                //본격적으로 루프 찾아서 제거하기
                for (int round = 1; round <= rightCount; round++)
                {
                    Console.WriteLine("round : " + round);
                    List<int[]> newRoundList = new List<int[]>();
                    foreach (int[] roundOrder in roundList)
                    {
                        int x = roundOrder[0];
                        int y = roundOrder[1];
                        if (order[x, y] == round)
                        {
                            for (int z = 1; z <= rightCount; z++)
                            {
                                if (order[y, z] > 0 && order[x, z] == 0 && x != z && y != z)
                                {
                                    order[x, z] = round + 1;
                                    newRoundList.Add(new int[2] { x, z });
                                    if (order[z, x] != 0) //루프일 경우
                                    {
                                        loop.Add(new int[2] { x, z });
                                    }
                                }
                            }
                        }
                    }
                    if (newRoundList.Count == 0)
                    { break; }
                    else
                    {
                        roundList = newRoundList;
                    }

                }
                //출력
                int count = 0;
                for (int z = 1; z <= rightCount; z++)
                {
                    if (order[0, z] == 0)
                    {
                        count++;
                    }
                }
                Console.WriteLine(loop.Count / 2 + "개의 루프 발견");
                Console.WriteLine(count);
                TestConsole.ReadLine();
            }
        }
    }
}
